package algorithm;

public class leetcode_0647 {
    public int countSubstrings(String s) {
        int len=s.length();
        int[][] dp=new int[len][len];
        boolean [][] flag=new boolean[len][len];
        for(int i=0;i<len-1;++i){
            dp[i][i]=1;
            flag[i][i]=true;
            if(s.charAt(i)==s.charAt(i+1)){
                dp[i][i+1]=3;
                flag[i][i+1]=true;
            }
            else{
                dp[i][i+1]=2;
            }
        }
        dp[len-1][len-1]=1;
        flag[len-1][len-1]=true;
        for(int j=2;j<len;++j){
            for(int i=0;i+j<len;++i){
                if(s.charAt(i)==s.charAt(i+j)){

                    dp[i][i+j]=dp[i][i+j-1]+dp[i+1][i+j]-dp[i+1][i+j-1];
                    if(flag[i+1][i+j-1]) {dp[i][i+j]+=1;flag[i][i+j]=true;}
                }
                else{
                    dp[i][i+j]=dp[i][i+j-1]+dp[i+1][i+j]-dp[i+1][i+j-1];
                }
            }
        }
        return dp[0][len-1];
    }
}
